package oj;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Num144 {
    //先序遍历的非递归实现
    List<Integer> ret=new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return ret;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            ret.add(treeNode.val);
            //先入右孩子，因为栈是先入后出，先序遍历要后打印右孩子，所以让右孩子先入
            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            if(treeNode.left!=null){
                stack.push(treeNode.left);
            }
        }
        return ret;
    }
}
